#include<stdio.h>

typedef char VertexType;		//顶点
typedef int EdgeType;

#define MAXSIZE 100

typedef struct {
  VertexType vertex[MAXSIZE];		//保存顶点
  EdgeType arc[MAXSIZE][MAXSIZE];		//记录两顶点之间边的关系(是否有边)
  int vertex_num;		//顶点数量
  int edge_num;			//边的数量
}Mat_Grph;		//矩阵的图

int visited[MAXSIZE];		//记录某个顶点是否被访问过

void creat_graph(Mat_Grph* G) {
  G->vertex_num = 9;	//9个节点
  G->edge_num = 15;		//15个无向边
  G->vertex[0] = 'A';
  G->vertex[1] = 'B';
  G->vertex[2] = 'C';
  G->vertex[3] = 'D';
  G->vertex[4] = 'E';
  G->vertex[5] = 'F';
  G->vertex[6] = 'G';
  G->vertex[7] = 'H';
  G->vertex[8] = 'I';

  for (int i = 0; i < G->vertex_num; i++) {		//赋值
    for (int j = 0; j < G->vertex_num; j++) {
      G->arc[i][j] = 0;
    }
  }

  //A-B,A-F是有线的
  G->arc[0][1] = 1;
  G->arc[0][5] = 1;

  //BC,BG,BI
  G->arc[1][2] = 1;
  G->arc[1][6] = 1;
  G->arc[1][8] = 1;

  //CD,CI
  G->arc[2][3] = 1;
  G->arc[2][8] = 1;

  //DE,DG,DH,DI
  G->arc[3][4] = 1;
  G->arc[3][6] = 1;
  G->arc[3][7] = 1;
  G->arc[3][8] = 1;

  //EF,EG
  G->arc[4][5] = 1;
  G->arc[4][7] = 1;

  //FG
  G->arc[5][6] = 1;

  //GH
  G->arc[6][7] = 1;

  //上下部分是对称的,把上半部分复制到下半部分
  for (int i = 0; i < G->vertex_num; i++) {		//赋值
    for (int j = 0; j < G->vertex_num; j++) {
      G->arc[j][i] = G->arc[i][j];
    }
  }

}

void dfs(Mat_Grph G, int i) {
  visited[i] = 1;		//已被访问
  printf("%c\n", G.vertex[i]);

  for (int j = 0; j< G.vertex_num; j++) {
    if (G.arc[i][j] == 1 && visited[j] == 0) {	//找到有连线且还没有被访问过的点
      dfs(G, j);
    }
  }
}

int main() {
  Mat_Grph G;
  creat_graph(&G);
  //初始化
  for (int i = 0; i < G.vertex_num; i++) {
    visited[i] = 0;
  }
  dfs(G, 0);		//从第一个顶点0开始
  return 0;
}